package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/10 11:25
 *
 动态规划：设dp为以数字arr[i]结尾的连续子数组和的最大值，当前面子数组和大于0时转移
 */

public class Main17 {
    public int FindGreatestSumOfSubArray(int[] array) {
        int dp[]=new int[array.length+1];
        int ans=Integer.MIN_VALUE;
        for(int i=1;i<=array.length;++i){
            if(dp[i-1]>0)dp[i]=dp[i-1]+array[i-1];
            else dp[i]=array[i-1];
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }


    public int FindGreatestSumOfSubArray2(int[] array) {
        //因为dpi只与dp[i-1]有关，所以可优化为常数
        int dp=0;
        int ans=Integer.MIN_VALUE;
        for(int i=1;i<=array.length;++i){
            if(dp>0)dp+=array[i-1];
            else dp=array[i-1];
            ans=Math.max(ans,dp);
        }
        return ans;
    }
    public static void main(String[] args) {
        int arr[]={1,-2,3,10,-4,7,2,-5};//18
        System.out.println(new Main17().FindGreatestSumOfSubArray2(arr));
    }
}
